package top.pmwly;

/**
 * @author Herther
 * @version 1.0.0
 * @ClassName insertionSort.java
 * @Description 插入排序
 * @createTime 2021年08月16日 14:54:00
 */
public class InsertionSort {

    private InsertionSort(){}

    public static <T extends Comparable> void sort(T[] data){
        // 5 2 3 1
        // 2 5 3 1
        // 2 3 5 1
        // 1 2 3 5
        for (int i=0; i< data.length; i++){
            for (int j = i; j-1 >= 0;j--){
                if (data[j].compareTo(data[j-1]) < 0 ){
                    swap(data,j,j-1);
                }else break;
            }
        }


    }
    //优化插入排序
    public static <T extends Comparable> void sort2(T[] data){
        // 5 2 3 1
        // 2 5 3 1
        // 2 3 5 1
        // 1 2 3 5
        for (int i=0; i< data.length; i++){
            T t = data[i];
            int j;
            for (j = i; j-1 >= 0 && t.compareTo(data[j-1]) < 0 ;j--){
                    data[j] = data[j-1];
            }
            data[j] = t;
        }
    }


    private static <T> void swap(T[] data, int i, int j) {
        T k = data[i];
        data[i] = data[j];
        data[j] = k;
    }

}
